import java.util.ArrayList;
import java.util.List;

/**
 * @author 03010570
 * @date 2020/07/14
 * describe:    LeetCode : 120、三角形最小路径和     https://leetcode-cn.com/problems/triangle/
 */
public class LeetCode_120 {
    public static void main(String[] args) {
        List<List<Integer>> list = new ArrayList<>();
        ArrayList<Integer> temp = new ArrayList<>();
        temp.add(-1);
        list.add(new ArrayList<>(temp));
        temp.clear();
        temp.add(-2);
        temp.add(-3);
        list.add(new ArrayList<>(temp));
        temp.clear();
//        temp.add(6);
//        temp.add(5);
//        temp.add(7);
//        list.add(new ArrayList<>(temp));
//        temp.clear();
//        temp.add(4);
//        temp.add(1);
//        temp.add(8);
//        temp.add(3);
//        list.add(new ArrayList<>(temp));
//        temp.clear();
//        for (List<Integer> integers : list) {
//            for (Integer integer : integers) {
//                System.out.print(integer + " ,");
//            }
//            System.out.println();
//        }
        System.out.println(minimumTotal(list));

    }

    /**
     * 自低向上计算：
     * 主要 数组的长度是 集合的长度+1，因为计算最后一个 值的时候需要赋值为 0
     * 一定满足 f[j] = Math.min(f[j] + f[j-1]) + t.get(i).get(j);
     * 那么最顶上的一个元素就是 最小值
     * 时间复杂度 ： O(N^2)
     * 空间复杂度 ： O(N)
     *
     * @param triangle
     * @return
     */
    public static int minimumTotal(List<List<Integer>> triangle) {
        int length = triangle.size();
        int[] res = new int[length + 1];
        for (int i = length - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                if (res[j + 1] < res[j]) {
                    res[j] = res[j + 1];
                }
                res[j] += triangle.get(i).get(j);
            }
        }
        return res[0];
    }

    /**
     * 同 方法1 ，从空间复杂度上进行优化
     * 初始化 res[0] = t.get(0).get(0)
     * 1、记录当前下标的上一个值 temp , res[0] += t.get(0).get(0)
     * 2、记录当前操作的值，给临时变量 ,上一行的值 preRow，操作完成再赋值给 temp,
     * 3、res[i] = temp + t.get(i).get(i)
     * <p>
     * 时间复杂度 ： O(N^2)
     * 空间复杂度 ： O(N) 集合的长度
     *
     * @param triangle
     * @return
     */
    public static int minimumTotal2(List<List<Integer>> triangle) {
        int[] res = new int[triangle.size()];
        res[0] = triangle.get(0).get(0);
        for (int i = 1; i < triangle.size(); i++) {
            int temp = res[0];
            res[0] += triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                int preRow = res[j];
                res[j] = Math.min(temp, res[j]) + triangle.get(i).get(j);
                temp = preRow;
            }
            res[i] = temp + triangle.get(i).get(i);
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < triangle.size(); i++) {
            if (min > res[i]) {
                min = res[i];
            }
        }
        return min;

    }


    /**
     * 二位矩阵，状态转移表
     * 状态转移方程：
     * 1、f[0][0] = t.get(0).get(0)
     * 2、f[i][0] = f[i-1][0] + t.get(i).get(0)
     * 3、f[i][j] = Math.min(f[i-1][j],f[i-1][j-1]) + t.get(i).get(j);
     * 4、f[i][i] = f[i-1][i-1] + t.get(i).get(i);
     * 最后比较最后一行的大小即可，最小值即为最小路径和
     * 时间复杂度 ： O(N^2)
     * 空间复杂度 ： O(N^2)
     *
     * @param triangle
     * @return
     */
    public static int minimumTotal1(List<List<Integer>> triangle) {
        int[][] res = new int[triangle.size()][triangle.size()];
        res[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < triangle.size(); i++) {
            res[i][0] = res[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                res[i][j] = Math.min(res[i - 1][j], res[i - 1][j - 1]) + triangle.get(i).get(j);
            }
            res[i][i] = res[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < triangle.size(); i++) {
            if (min > res[triangle.size() - 1][i]) {
                min = res[triangle.size() - 1][i];
            }
        }
        return min;
    }
}
